Tower of Hanoi is a popular math puzzle in which we have given 3 towers and one of those towers has n number of rings of a different shape. We need to move those rings from one tower to another and collect all rings in another tower in the exact same sequence. All the rings are of different sizes and stacked in ascending order on one of the towers. The number of rings may be changed for various puzzles but the number of towers will remain the same 3. There are 3 simples rules we need to follow when we solve this problem:
- We can move only one ring at a time
- We can only move the upper ring from any tower and move it to another tower
- No larger ring may be placed on the top of a smaller one.
Algorithm:
- We have 3 towers so towers naming will be the source, destination, and auxiliary.
- The source tower would be that tower which contains all the rings in ascending order from top to bottom in first place.
- The destination would be that tower in which we will move all the rings and placed those in the same order as they are in source tower.
- Auxiliary tower will help to move rings from one place to another.
Time Complexity = O(2 n ) where n is the number of rings Space complexity = O(n)
Ps eudocode for Tower of Hanoi
tower(number_of_rings, source, auxiliary, destination) IF numbe_of_rings == 1 move disk from source to destination ELSE tower(number_of_rings - 1, source, destination, auxiliary) move disk from source to destination tower(number_of_rings - 1, auxiliary, source, destination)
Tower of Hanoi for 3 rings
Python:
def T_O_H(n , source, destination,auxiliary):
if n == 1:
print("Move ring 1 from ",source,"to",destination)
return
T_O_H(n-1, source, auxiliary, destination)
print ("Move ring",n,"from",source,"to", destination)
T_O_H(n-1, auxiliary, destination, source)
n = int(input("Enter the number of Rings: "))
TowerOfHanoi(n, 'SOURCE', 'DESTINATION', 'AUXILIARY')
Output:
Enter the number of Rings: 3 Move ring 1 from SOURCE to DESTINATION Move ring 2 from SOURCE to AUXILIARY Move ring 1 from DESTINATION to AUXILIARY Move ring 3 from SOURCE to DESTINATION Move ring 1 from AUXILIARY to SOURCE Move ring 2 from AUXILIARY to DESTINATION Move ring 1 from SOURCE to DESTINATION
People are also reading: